// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-14 14:08
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DynamicPlan;

public class MinPathSum {
    /**
     * 最短路径和
     *
     * @param grid 节点权值
     * @return 返回最小路径和
     */
    public int minPathSum(int[][] grid) {
        /*
            1 朴素方法 -> 深度优先遍历 + 回溯 + 动态规划
            2 状态 -> 当前节点的路径和
            3 状态转移 -> 节点向右移动&&向下移动,从开始节点到结束节点，当前节点和最短路径和左边节点以及上边节点的最短路径有关
            4 输出 ->  dp[m-1][n-1]，dp状态数组记录的每一个节点的从开始节点到当前节点的最小路径
            5 初始状态 -> dp[0][0] = grid[0][0] 起始节点最短路径对应自己的权值大小，因为不用移动,矩阵的边缘的最短路径是固定的
         */
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        // 状态初始化
        dp[0][0] = grid[0][0];
        // 矩阵边缘初始化
        for (int i = 1; i < m; i++) {
            // 第一列初始化
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < n; i++) {
            // 第一行初始化
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }

        for (int i = 1; i < m; i++) {
            /*
                 dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
             */
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
}
